// 120.三角形最小路径和
package Leetcode_Second_Brush;

import java.util.Collections;
import java.util.List;

public class Solution120 {
public int minimumTotal(List<List<Integer>> triangle) {
    // 从第二层开始遍历每一层
    for (int i = 1; i < triangle.size(); i++) {
        for (int j = 0; j < triangle.get(i).size(); j++) {
            // 当前层的第一个元素
            if (j == 0) {
                triangle.get(i).set(j, triangle.get(i).get(j) + triangle.get(i - 1).get(0));
            } 
            // 当前层的最后一个元素
            else if (j == triangle.get(i).size() - 1) {
                triangle.get(i).set(j, triangle.get(i).get(j) + triangle.get(i - 1).get(triangle.get(i - 1).size() - 1));
            } 
            // 其他元素
            else {
                triangle.get(i).set(j, triangle.get(i).get(j) + Math.min(triangle.get(i - 1).get(j - 1), triangle.get(i - 1).get(j)));
            }
        }
    }

    // 找到最后一层中的最小值
    return Collections.min(triangle.get(triangle.size() - 1));
}
}
